<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from tp.tnf on 19 December 2010 -->

<TITLE>Tree Parsing - Summary of the Specification Language</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>Tree Parsing</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_3.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_5.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<A NAME="IDX38"></A>
<H1><A NAME="SEC13" HREF="tp_toc.html#SEC13">Summary of the Specification Language</A></H1>
<P>
The phrase structure of the specification language is described by the
following ambiguous grammar:
<P>
<PRE>
Source: (Include / Declaration / Rule)+ .

Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .

Rule:
  Nonterm '::=' Node    (':' / '::') Action ['COST' Integer] ';' /
  Nonterm '::=' Nonterm  ':'         Action ['COST' Integer] ';' /
  Nonterm '::=' Fragment ':'         Action ['COST' Integer] ';' .
Action: Identifier .

Node:
  Terminal /
  Terminal '(' Nonterm [',' Nonterm] ')' /
  Terminal '(' (Type // ',') ')' /
  Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .

Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .
</PRE>
<P>
Declarations and rules are the main components of a specification.
Includes are simply names of files that are needed to define the
identifiers representing types and actions.
<A NAME="IDX39"></A>
<P>
An <CODE>Include</CODE> is a sequence of characters delimited by quotation marks
(<KBD>"</KBD>).
It is used unchanged in an <CODE>#include</CODE> directive output by the
specification language translator.
Only one <CODE>#include</CODE> directive is output for each distinct
<CODE>Include</CODE>, regardless of how many times that <CODE>Include</CODE> appears in
the specification.
<A NAME="IDX40"></A>
<P>
An <CODE>Identifier</CODE> is a sequence of letters and digits, the first of
which is a letter.
As in C, the underscore (<KBD>_</KBD>) is considered a letter.
<P>
<A NAME="IDX41"></A>
<H2><A NAME="SEC14" HREF="tp_toc.html#SEC14">Declarations</A></H2>
<P>
Each nonterminal symbol must be declared, stating the type of the value
associated with it:
<P>
<PRE>
Declaration: (Nonterm // ',') ':' Type ';' .
Nonterm: Identifier .
Type: Identifier .
</PRE>
<P>
Types are always represented by identifiers.
If the type is a C basic type, no further declaration is necessary.
Other types must be defined by a
<A NAME="IDX42"></A>
<CODE>typedef</CODE> construct that appears in
some file named by an <CODE>Include</CODE>
(see  <A HREF="tp_4.html#SEC13">Summary of the Specification Language</A>).
<P>
Here is a set of declarations that is appropriate for the examples given
earlier in this document:
<P>
<PRE>
IntLit: int;
IntReg, FltReg: reg;  "mydefs.h"
</PRE>
<P>
Because <CODE>int</CODE> is a C basic type, no further information is necessary.
<CODE>reg</CODE>, on the other hand, is declared by a <CODE>typedef</CODE>
construct that appears in file <TT>`mydefs.h'</TT>.
Thus the <CODE>Include</CODE> <SAMP>`"mydefs.h"'</SAMP> is used to provide access to
that information.
<P>
<A NAME="IDX43"></A>
<H2><A NAME="SEC15" HREF="tp_toc.html#SEC15">Rules</A></H2>
<P>
As discussed earlier, there are three kinds of rules:
node rules (see  <A HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>),
chain rules (see  <A HREF="tp_2.html#SEC7">Chain Rules</A>), and
fragment rules (see  <A HREF="tp_2.html#SEC8">Rules Describing Tree Fragments</A>):
<P>
<PRE>
Rule:
  Nonterm '::=' Node    (':' / '::') Action ['COST' Integer] ';' /
  Nonterm '::=' Nonterm  ':'         Action ['COST' Integer] ';' /
  Nonterm '::=' Fragment ':'         Action ['COST' Integer] ';' .
Action: Identifier .
</PRE>
<P>
Each rule has an associated
<A NAME="IDX44"></A>
action and an optional
<A NAME="IDX45"></A>
cost (which defaults to 1 if not specified).
The action is defined by an identifier, which must be defined in the
file described by one of the <CODE>Include</CODE> components of the
specification.
That definition might be an <CODE>extern</CODE> statement or a <CODE>#define</CODE>
directive (see  <A HREF="tp_3.html#SEC11">Implementing Actions</A>).
The signature of the action is determined by the type of the left-hand-side
<CODE>Nonterm</CODE> and the right-hand side as discussed above
(see  <A HREF="tp_3.html#SEC10">Actions and Values</A>).
<A NAME="IDX46"></A>
<P>
A node rule describes a single, possibly decorated, node of the tree being
parsed (see  <A HREF="tp_2.html#SEC6">Rules Describing Tree Nodes</A>):
<P>
<PRE>
Node:
  Terminal /
  Terminal '(' Nonterm [',' Nonterm] ')' /
  Terminal '(' (Type // ',') ')' /
  Terminal '(' Nonterm [',' Nonterm] ',' (Type // ',') ')' .
Terminal: Identifier .
</PRE>
<A NAME="IDX47"></A>
<P>
<CODE>Terminal</CODE> is the symbol of the
<A NAME="IDX48"></A>
ranked alphabet that is represented by the node.
The <CODE>Node</CODE> must have <VAR>k</VAR> <CODE>Nonterm</CODE> children if
<CODE>Terminal</CODE> has arity <VAR>k</VAR>.
<P>
Each <CODE>Terminal</CODE> is also associated with a specific set
(possibly empty) of
<A NAME="IDX49"></A>
attributes.
There is no limit to the number or types of the attributes decorating a
node.
Each attribute is denoted by a <CODE>Type</CODE>, which must be either a C basic
type or an identifier defined by a <CODE>typedef</CODE> construct that appears in
some file named by an <CODE>Include</CODE>
(see  <A HREF="tp_4.html#SEC13">Summary of the Specification Language</A>).
<P>
The <CODE>::</CODE> marker distinguishes a
<A NAME="IDX50"></A>
commutative node (see  <A HREF="tp_3.html#SEC12">Commutative Actions</A>).
This node must have two children, and those children must be distinct
nonterminals.
A commutative node rule may have arbitrary decorations.
<P>
A fragment rule describes a fragment consisting of two or more adjacent
nodes:
<P>
<PRE>
Fragment: Terminal '(' Child [',' Child] ')' .
Child: Nonterm / Fragment .
</PRE>
<P>
Nodes participating in fragments may not be decorated.
There is no limit on the size of a fragment.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_3.html"><IMG SRC="gifs/prev.gif" ALT="Previous Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_5.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="tp_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
